IOI2020连接擎天树题解

题意：一个 $n$ 个点的图，给定了任意两点之间的不同简单路数量 $a_{ij}$，简单路定义为不经过重复点的路径，保证$0\le a_{ij}\le 3$。求构造满足要求的图或判断无解。

画几张图观察一下简单路的性质，发现合法的图一定满足任意一个连通块中最多只有一个环。如果一个连通块有不止一个环，一定可以找到一对点存在至少四条不同简单路，如下图：

那么一个连通块一定是树或者基环树。dfs 出每个连通块，先判断一下如果连通块里出现了路径数为 $0$ 的点对就是无解。然后树非常好处理，如果连通块内路径数全是 $1$ 那就是树，随便构造一个就行。基环树复杂一些，我们画张图：

观察发现，如果两个点在同一个红圈里，那它们只间有 $1$ 条简单路，否则有 $2$ 条。$3$ 是绝对不会出现的，出现了直接无解。然后 dfs 出每个连通块里，由 $a_{ij}=1$ 相连的子连通块，它们应该在一个红圈里。如果一个红圈里混进了路径数为 $2$ 的点对那无解，否则把它们连成一棵树。最后在每个红圈里找一个代表点，把这些代表点串起来成为一个环即可。如果代表点不足三个就没法串成环，还是无解。

#include "supertrees.h"
#define N 1000
std::vector<std::vector<int>> *G, ret;
void addedge(int x, int y) {
	ret[x][y] = ret[y][x] = 1;
}
int n, mx; char vis[N];
std::vector<int> cnt, all, sm;
void dfs(int x) {
	vis[x] = 1;
	cnt.push_back(x);
	for (int i = 0; i < n; i++) {
		int d = (*G)[x][i];
		mx = std::max(d, mx);
		if (!vis[i] && d) dfs(i);
	}
}
void dfsS(int x) {
	vis[x] = 2;
	sm.push_back(x);
	for (int i = 0; i < n; i++) {
		if (vis[i] == 1 && (*G)[x][i] == 1) dfsS(i);
	}
}
int construct(std::vector<std::vector<int>> p) {
	G = &p; n = p.size();
	ret.resize(n);
	for (int i = 0; i < n; i++)
		ret[i].resize(n);
	for (int i = 0; i < n; i++) if (!vis[i]) {
		mx = 1;
		cnt.clear();
		dfs(i);
		if (mx == 3) return 0;
		for (int i = 1; i < cnt.size(); i++)
			for (int j = 0; j < i; j++)
				if (p[cnt[i]][cnt[j]] == 0)
					return 0;
		if (mx == 1) {
			for (int i = 1; i < cnt.size(); i++)
				addedge(cnt[0], cnt[i]);
			continue;
		}
		all.clear();
		for (int j : cnt) if (vis[j] == 1) {
			sm.clear();
			dfsS(j);
			for (int i = 1; i < sm.size(); i++) {
				for (int j = 0; j < i; j++)
					if (p[sm[i]][sm[j]] != 1)
						return 0;
				addedge(sm[0], sm[i]);
			}
			all.push_back(sm[0]);
		}
		if (all.size() <= 2) return 0;
		for (int j = 1; j < all.size(); j++)
			addedge(all[j-1], all[j]);
		addedge(all[0], all.back());
	}
	build(ret);
	return 1;
}